﻿#include <iostream>
#include <map>
using namespace std;
// pair的底层
//typedef pair<const Key, T> value_type;
//template <class T1, class T2>
//struct pair
//{
//	typedef T1 first_type;
//	typedef T2 second_type;
//	T1 first;
//	T2 second;
//	pair() : first(T1()), second(T2())
//	{
//	}
//	pair(const T1& a, const T2& b) : first(a), second(b)
//	{
//	}
//	template<class U, class V>
//	pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
//	{
//	}
//};
//template <class T1, class T2>
//inline pair<T1, T2> make_pair(T1 x, T2 y)
//{
//	return (pair<T1, T2>(x, y));
//}

void test1()
{
	map<string, string> m;
	pair<string, string> word1("hello", "你好");
	m.insert(word1); //插入有名对象
	m.insert(pair<string, string>("eat", "吃"));//插入匿名对象
	m.insert(make_pair("bad", "坏的"));//调用make_pair
	m.insert({ "cat", "猫" });
	m.insert({ "cat", "猫科动物" }); //新插入的
	auto it = m.begin();
	while (it != m.end())
	{
		//it->first += 'z'; //不可修改
		it->second += 'z';//可修改

		cout << it->first << ":" << it->second << endl;
		it++;
	}
	cout << endl;
}
void test2()
{
	map<string, string> m = { {"hello", "你好"},  {"eat", "吃"},
						  {"bad", "坏的"}, {"cat", "猫"} };
	auto it = m.begin();
	while (it != m.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}
	cout << endl;
	auto left = m.begin()++;
	auto right = m.end()--;
	m.erase(left, right);
	it = m.begin();
	while (it != m.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}

	/*m.erase(m.begin());
	it = m.begin();
	while (it != m.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}*/

}


void test3()
{
	multimap<char, int> mymm;

	mymm.insert(pair<char, int>('a', 10));
	mymm.insert(pair<char, int>('b', 20));
	mymm.insert(pair<char, int>('b', 30));
	mymm.insert(pair<char, int>('b', 40));
	mymm.insert(pair<char, int>('c', 50));
	mymm.insert(pair<char, int>('c', 60));
	mymm.insert(pair<char, int>('d', 60));

	cout << "mymm contains:" << endl;
	for (char ch = 'a'; ch <= 'd'; ch++)
	{
		pair <multimap<char, int>::iterator, multimap<char, int>::iterator> ret;
		ret = mymm.equal_range(ch);
		cout << ch << " =>";
		for (multimap<char, int>::iterator it = ret.first; it != ret.second; ++it)
			cout << ' ' << it->second;
		cout << endl;
	}

}

void test4()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
	"苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		/*auto ret = countMap.find(str);
		if (ret == countMap.end())
		{
			countMap.insert({ str, 1 });
		}
		else
		{
			ret->second++;
		}*/
		countMap[str]++; //用[]
	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	
	//// operator的内部实现
	//mapped_type& operator[] (const key_type& k)
	//{
	//	pair<iterator, bool> ret = insert({ k, mapped_type() });
	//	iterator it = ret.first;
	//	return it->second;
	//}
}


void test5()
{
	////作业
	//class Solution
	//{
	//public:
	//	struct mycompare
	//	{
	//		bool operator()(const pair<string, int>& p1, const pair<string, int>& p2) const
	//		{
	//			return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);
	//		}
	//	};

	//	vector<string> topKFrequent(vector<string>& words, int k)
	//	{
	//		map<string, int> m;
	//		for (auto s : words)
	//		{
	//			m[s]++;
	//		}

	//		vector<pair<string, int>> v(m.begin(), m.end());
	//		sort(v.begin(), v.end(), mycompare());
	//		//stable_sort(v.begin(), v.end(), mycompare());

	//		vector<string> ret;
	//		for (int i = 0; i < k; i++)
	//		{
	//			ret.push_back(v[i].first);
	//		}
	//		return ret;
	//	}
	//};
}

int main()
{
	map<string, string> mymap;
	mymap.insert({ "hello", "你好" });

	//key不存在 -> 插入
	mymap["cat"]; 

	//key不存在 -> 插入+修改
	mymap["right"] = "右边";

	//key存在 -> 修改
	mymap["right"] = "正确的";

	//查找不存在的key
	cout << mymap["left"] << endl;
	//查找存在的key
	cout << mymap["right"] << endl;
	
	return 0;
}

